package day1_array.leetcode.sliding_window;

/**
 * @Author: yuisama
 * @Date: 2022/9/8 11:14
 * @Description:滑动窗口解决最小覆盖子串问题
 */
public class Num76_MinWindow {
    public String minWindow(String s, String t) {
        // 需要的字符
        int[] needs = new int[256];
        // 当前窗口满足的字符
        int[] windows = new int[256];
        int left = 0,right = 0;
        // 记录最小覆盖子串的起始索引以及长度
        int start = 0,len = Integer.MAX_VALUE;
        // 窗口windows中满足的字符个数
        int valid = 0;
        // 初始化需要的字符数组
        // needsSize为不重复的字符个数
        int needsSize = 0;
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            needs[c - 'A'] ++;
            if (needs[c - 'A'] == 1) {
                needsSize ++;
            }
        }
        // right走到终点，整个s扫描完毕
        while (right < s.length()) {
            // c是即将移入窗口的字符
            char c = s.charAt(right);
            // 右移窗口
            right ++;
            // 更新窗口,字符c是满足的字符
            // ... 更新模板
            if (needs[c - 'A'] > 0) {
                windows[c - 'A'] ++;
                // 只有当需求字符出现次数和窗口字符出现次数相同，才是有效字符
                // 此处不能直接valiad++，避免多个重复字符在窗口中的情况！
                if (needs[c - 'A'] == windows[c - 'A']) {
                    valid ++;
                }
            }
            // 窗口添加新字符后校验左侧窗口是否需要移动
            // valid表示windows窗口中有效键值对个数
            while (valid == needsSize) {
                // 只有当窗口中有效字符数与t长度相同，此时窗口中都是满足的字符串
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d是即将移除的字符
                char d = s.charAt(left);
                left ++;
                // 窗口数据更新
                // 模板更新代码
                if (needs[d - 'A'] > 0) {
                    if (windows[d - 'A'] == needs[d - 'A']) {
                        // 此时窗口中有效字符数量与需求数量相同，有效字符个数-1
                        // 说明此时左侧窗口不再移动
                        valid --;
                    }
                    windows[d - 'A'] --;
                }
            }
        }
        return len == Integer.MAX_VALUE ? "" : s.substring(start,start + len);
    }
}
